package open.algo.search;

import java.util.Arrays;

import open.algo.sort.Swap;

/**
 * http://en.wikipedia.org/wiki/Median_search
 * 
 * @author leef
 * 
 */
public class Median {

	static class M {
		int first;
		int second;

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + first;
			result = prime * result + second;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			M other = (M) obj;
			if (first != other.first)
				return false;
			if (second != other.second)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return "M [first=" + first + ", second=" + second + "]";
		}

	}

	interface Find {
		/**
		 * for even size, there are two median
		 * 
		 * @param array
		 * @return
		 */
		public M median(int[] array);
	}

	static class Find1 implements Find {
		/**
		 * sort first, then get median.
		 * 
		 * quick sort average time: O(nlogn), quick sort worst time: O(n^2)
		 */
		@Override
		public M median(int[] array) {
			Arrays.sort(array);
			M m = new M();

			if (array.length % 2 == 0) {
				m.first = array[array.length / 2 - 1];
				m.second = array[array.length / 2];
			} else {
				m.first = array[array.length / 2];
			}

			return m;
		}
	}

	static class Find2 implements Find {

		/**
		 * 
		 * 
		 */
		@Override
		public M median(int[] array) {
			int s_size_sum = array.length / 2;
			if (array.length % 2 != 0)
				return median(array, s_size_sum);
			else {
				M m1 = median(array, s_size_sum);
				M m2 = median(array, s_size_sum - 1);
				M m = new M();
				m.first = m2.first;
				m.second = m1.first;

				return m;
			}
		}

		/**
		 * 
		 * similar to quick sort,
		 * 
		 * <pre>
		 * 1) each round, use a pivot to divide the array[s, e], m_size 
		 * 2) count the number for those < pivot
		 * 	2.1) if number == m_size, we get it, return pivot
		 *  2.2) if number > m_size, find it in the small part, array[0, pivot_pos),  
		 *  2.3) if number < m_size, find it in the big part, array(pivot_pos, n-1], m_size -= (s_size + 1)
		 * </pre>
		 * 
		 * average time: O(n) worst time: O(n^2)
		 * 
		 * @param array
		 * @param s_size_sum
		 * @return
		 */
		public M median(int[] array, int s_size_sum) {
			M target = new M();

			int s = 0;
			int e = array.length - 1;
			int m = (s + e) / 2;

			while (s <= e) {
				m = (s + e) / 2;
				int pivot = array[m];

				// quick sort partition
				Swap.swap(array, m, e);
				int j = s;
				for (int i = s; i < e; i++) {
					if (array[i] < pivot) {
						Swap.swap(array, i, j++);
					}
				}
				Swap.swap(array, j, e);
				// quick sort partition

				int s_size = j - s;

				if (s_size == s_size_sum) {
					target.first = pivot;
					break;
				} else if (s_size > s_size_sum) {
					e = j - 1;
				} else {
					s = j + 1;
					s_size_sum -= (s_size + 1);
				}
			}

			return target;
		}
	}

}
